import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

public class SolutionOffer51 {

    static class BIT{

        int[] h;
        int n;

        public BIT(int n){
            this.n=n;
            h=new int[n+1];
        }

        public void update(int x){
            while (x<=n){
                h[x]+=1;
                x+=lowbit(x);
            }
        }

        public int query(int x){
            int t=0;
            while (x>0){
                t+=h[x];
                x-=lowbit(x);
            }
            return t;
        }

        private int lowbit(int x) {
            return x&(-x);
        }
    }

    public int reversePairs(int[] nums) {
        TreeSet<Integer> set=new TreeSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int id=0;
        Map<Integer,Integer> map=new HashMap<>();
        for (Integer integer : set) {
            id++;
            map.put(integer,id);
        }
        BIT bit=new BIT(id);
        int ans=0;
        for (int i=0;i<nums.length;i++){
            ans=ans+i-bit.query(map.get(nums[i]));
            bit.update(map.get(nums[i]));
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new SolutionOffer51().reversePairs(new int[]{7,5,6,4}));
    }
}
